💰 Coin Change I - Minimum Coins

Find the fewest number of coins to make a target amount

👩‍💻 Minimum Coin Challenge

🎯 The Mission:

Find the minimum number of coins needed to make a target amount using an infinite supply of given coin denominations with dynamic programming. Return -1 if impossible.

📋 Requirements:

  • Minimize the number of coins for the target amount
  • Use coins with infinite supply
  • Each coin has a denomination value
  • Output the minimum number of coins or -1 if impossible

Input/Output Specifications

  • Input: Space-separated coin denominations, followed by the target amount
  • Output: Minimum number of coins (integer) or -1 if impossible
  • Constraints: 1 ≤ coins.length ≤ 12, 0 ≤ amount ≤ 10^4

Example 1: coins=[1,2,5], amount=11

Coins:

1
2
5

Output: 3 (5+5+1)

Example 2: coins=[1], amount=0

Coins:

1

Output: 0

Example 3: coins=[2], amount=3

Coins:

2

Output: -1

⚡ Dynamic Programming Explained

How Dynamic Programming Works for Coin Change I

  1. Initialize: Create a DP array where dp[i] is the minimum number of coins for amount i
  2. Base Case: Set dp[0] = 0 (no coins for amount 0), others to INF
  3. Iterate Amounts: For each amount i and coin c, update dp[i] = min(dp[i], dp[i - c] + 1) if i - c >= 0
  4. Output: dp[amount] or -1 if it remains INF

Example DP Table (coins=[1,2], amount=3)

Amount0123
DP State0112

Output: 2 (ways: [1,1])

Time Complexity

O(n * amount)

Iterate over n coins and amount values

Space Complexity

O(amount)

For the DP array

Why Dynamic Programming?

  • ✅ Finds minimum coins efficiently
  • ✅ Handles infinite coin supply
  • ✅ Avoids redundant calculations
  • ❌ Large amount increases space usage

🔍 Step-by-Step Dynamic Programming Demo

Click "Start Demo" to begin step-by-step visualization

Algorithm Progress:

1. Display input coins and amount
2. Initialize DP array
3. Process amounts
4. Display result

Current Coins:

DP Table:

🎮 Practice Coin Change I

Enter inputs, then click "Compute Minimum Coins"

Test Cases

Example 1: coins=[1,2,5], amount=11 → 3 (5+5+1)

Example 2: coins=[1], amount=0 → 0

Example 3: coins=[2], amount=3 → -1

📊 Algorithm Analysis

Dynamic Programming Process

  1. Initialize: Set dp[0] = 0, others to INF
  2. Iterate Amounts: For each amount i and coin c, update dp[i] = min(dp[i], dp[i - c] + 1) if i - c >= 0
  3. Output: dp[amount] or -1 if INF

Time Complexity

O(n * amount)

Iterate over n coins and amount values

Space Complexity

O(amount)

For the DP array

Key Points

  • Dynamic Programming: Minimizes coins needed
  • Infinite Supply: Allows reusing coins
  • Applications: Currency systems, optimization problems
  • Limitation: Large amount increases space usage